Merkle trees are often used for memory authentication. A Merkle tree is a tree of Message Authentication Codes (MACs) that is computed over the replay-protected memory. The root of the Merkle tree is stored securely in an on-chip register in the processor. When a memory data line is accessed, its integrity is verified by checking its chain of MACs to the root of the Merkle tree. This approach, however, can result in significant performance and storage overheads due to the large number of MACs that need to be potentially fetched to verify the integrity of the memory data line.
To optimize the process, the MAC values can be cached in the Last Level Cache (LLC) and the verification stops on finding the first MAC along the tree in the LLC. While this approach reduces the performance overheads by reducing the number of MACs that need to fetched and computed to verify the memory data line, it disturbs the contents of the LLC.